package main

import (
	"fmt"
	"sort"
)

/*
两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。

说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
*/

//使用map
//func intersect(nums1 []int, nums2 []int) []int {
//	var NodeList []int
//	m1 :=make(map[int]int,999)
//	//遍历nums1 将元素存在map中 key为数组中的元素 value为该元素出现的次数
//	for _,i:=range nums1{
//		m1[i]=m1[i]+1
//	}
//	for _,j:=range nums2{
//		for key:=range m1{
//			if m1[key]>0&&j == key{
//				m1[key]=m1[key]-1
//				NodeList = append(NodeList,j)
//			}
//		}
//	}
//	return NodeList
//}

//双指针
func intersect(nums1 []int, nums2 []int) []int {
	var (
		list   []int
		n1, n2 int
	)
	sort.Ints(nums1) //[0,1,1,2,2,6,8,8,9]
	sort.Ints(nums2) //[2,2,7,8,9]

	for n1 < len(nums1) && n2 < len(nums2) {
		if nums1[n1] == nums2[n2] { //如果两个数相同 两个指针向右移动
			list = append(list, nums1[n1])
			n1++
			n2++
		} else if nums1[n1] > nums2[n2] {
			n2++
		} else {
			n1++
		}
	}
	return list
}

func main() {
	nums1 := []int{1, 2}
	nums2 := []int{1, 1}
	fmt.Println(intersect(nums1, nums2))
}
